In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a semi-symmetric graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

that is

edge-transitive In geometry, a polytope (for example, a polygon or a polyhedron) or a tiling is isotoxal () or edge-transitive if its symmetries act transitively on its edges. Informally, this means that there is only one type of edge to the object: given t ...

and regular, but not

vertex-transitive In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face in ...

. In other words, a graph is semi-symmetric if each vertex has the same number of incident edges, and there is a symmetry taking any of the graph's edges to any other of its edges, but there is some pair of vertices such that no symmetry maps the first into the second.

Properties

A semi-symmetric graph must be bipartite, and its

automorphism group In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...

must act transitively on each of the two vertex sets of the bipartition (in fact, regularity is not required for this property to hold). For instance, in the diagram of the Folkman graph shown here, green vertices can not be mapped to red ones by any automorphism, but every two vertices of the same color are symmetric with each other.

History

Semi-symmetric graphs were first studied E. Dauber, a student of F. Harary, in a paper, no longer available, titled "On line- but not point-symmetric graphs". This was seen by

Jon Folkman Jon Hal Folkman (December 8, 1938 – January 23, 1969) was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation. Schooling Folkman was a Putnam Fellow in 1960. He received his Ph.D. in 1964 from Pr ...

, whose paper, published in 1967, includes the smallest semi-symmetric graph, now known as the Folkman graph, on 20 vertices. The term "semi-symmetric" was first used by Klin ''et al.'' in a paper they published in 1978.

Cubic graphs

The smallest cubic semi-symmetric graph (that is, one in which each vertex is incident to exactly three edges) is the

Gray graph Grey (more common in British English) or gray (more common in American English) is an intermediate color between black and white. It is a neutral or achromatic color, meaning literally that it is "without color", because it can be composed o ...

on 54 vertices. It was first observed to be semi-symmetric by . It was proven to be the smallest cubic semi-symmetric graph by

Dragan Marušič Dragan Marušič (born 1953, Koper, Slovenia) is a Slovene mathematician. Marušič obtained his BSc in technical mathematics from the University of Ljubljana in 1976, and his PhD from the University of Reading in 1981 under the supervision of C ...

and Aleksander Malnič. All the cubic semi-symmetric graphs on up to 10000 vertices are known. According to Conder, Malnič, Marušič and Potočnik, the four smallest possible cubic semi-symmetric graphs after the Gray graph are the Iofinova–Ivanov graph on 110 vertices, the

Ljubljana graph In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges. It is a cubic graph with diameter 8, radius 7, chromatic number 2 and chromatic index 3. Its girth is 10 and there ...

on 112 vertices,. a graph on 120 vertices with girth 8 and the

Tutte 12-cage In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte. The Tutte 12-cage is the unique (3-12)- cage . It was discovered by C. T. Benson in 1966. ...

References

External links

*{{mathworld , urlname = SemisymmetricGraph , title = Semisymmetric Graph Algebraic graph theory Graph families Regular graphs